package bintree.leetcode;

/**
 * @Author: yuisama
 * @Date: 2022/9/19 14:29
 * @Description:最长同值路径
 */
public class Num687_LongestUniValuePath {
    int res = 0;
    public int longestUnivaluePath(TreeNode root) {
        if (root == null) {
            return 0;
        }
        oneSideLongestPath(root,root.val);
        return res;
    }
    /**
     * 以当前root为根节点的二叉树中，返回和父节点parentVal相同的同值单边最长路径
     * @param root 当前树的树根
     * @param parentVal 父节点值
     * @return
     */
    public int oneSideLongestPath(TreeNode root,int parentVal) {
        if (root == null) {
            return 0;
        }
        // 先要走到叶子节点
        int leftSide = oneSideLongestPath(root.left,root.val);
        int rightSide = oneSideLongestPath(root.right,root.val);
        // 后序位置
        // 每遍历完一颗子树，顺带求最大同值最长路径,此时计算的是以当前root为树根的左右子树之中同值最长路径
        // 计算完成之后再向上看当前节点和父节点是否相同
        res = Math.max(res,leftSide + rightSide);
        // 当前树根和父节点值都不相同，同值单边路径长度为0
        if (root.val != parentVal) {
            return 0;
        }
        // 单边最长路径为左右子树最长树枝 + 1
        return 1 + Math.max(leftSide,rightSide);
    }
}
